package 力扣_树算法.遍历;

import java.util.*;

/**二叉树的前序遍历
 * @author zx
 * @create 2022-04-09 10:26
 */
public class 二叉树的前序遍历_144 {
    public List<Integer> preorderTraversal2(TreeNode root) {
        //迭代
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        //栈的作用是用来短暂的保存遍历节点的值，以助于最后值的返回
        while(!stack.isEmpty() || root != null){
            while(root != null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            //将那个null弹出
            root = stack.pop();
            root = root.right;
        }
        return list;
    }
    /**
     * @return 递归
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        //递归
        List<Integer> res = new ArrayList<>();
        preOrder(root,res);
        return res;
    }
    private void preOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
